/*
https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence/solution/de-dao-zi-xu-lie-de-zui-shao-cao-zuo-ci-hefgl/
 */
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1713 {
    public int minOperations(int[] target, int[] arr) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<target.length;i++){
            map.put(target[i],i+1);
        }
        List<Integer> list=new ArrayList<>();
        for (int i : arr) {
            if (map.containsKey(i)){
                list.add(map.get(i));
            }
        }
        int[] d=new int[target.length];
        int len=0;
        for (Integer integer : list) {
            if (integer>d[len]){
                len++;
                d[len]=integer;
            }else{
                int l=0,r=len-1;
                while (l<r){
                    int mid=(l+r)/2;
                    if (integer<=d[mid]){
                        r=mid-1;
                    }else{
                        l=mid;
                    }
                    if (r-l==1){
                        if (d[r]<integer && d[r+1]>=integer){
                            l=r;
                        }else{
                            r=l;
                        }
                    }
                }
                d[l+1]=integer;
            }
        }
        return target.length-len;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1713().minOperations(new int[]{11,16,20,1,2,13,7,6,12,3},new int[]{11,13,3,7,7,1,10,12,14,1}));
    }
}
